package oct2013.linkednode;


public class FlattenBinaryTreetoLinkedList {
	public void flatten(TreeNode root) {
		TreeNode cur = root;
		TreeNode left;
		while (cur != null) {
			left = cur.left;
			if (left != null) {
				while (left.right != null)
					left = left.right;
				left.right = cur.right;
				cur.right = cur.left;
				cur.left = null;
			}
			cur = cur.right;
		}
	}

	/** recursive version */
	TreeNode prev;

	public void flattenRecursive(TreeNode root) {
		prev = new TreeNode(0);
		preorder(root);
	}

	void preorder(TreeNode root) {
		if (root == null)
			return;
		prev.right = root;
		prev.left = null;
		prev = root;
		TreeNode right = root.right;
		preorder(root.left);
		preorder(right);
	}
}
